package com.sourcetrip.algorithm.graph;

import com.sourcetrip.algorithm.inter.Graph;
import com.sourcetrip.algorithm.inter.UnionFindCustomedObject;
import com.sourcetrip.algorithm.unionfind.UnionFindCustomedObjectWithQuickUnion;
import com.sourcetrip.my.modle.EdgeInfo;
import com.sourcetrip.my.modle.PathInfo;
import com.sourcetrip.utils.Visitor;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/8
 * @description: 图的实现之-邻接表 --
 * 也可以用 邻接矩阵（Adjacency Matrix），但是由于冗余数据多，不做实现。
 * --
 * 设计中需要考虑的问题：
 * 1.是否可以重复加入顶点（由于在二维的图中，顶点位置可以多样，但是在简单图中，可能不会考虑位置的信息！）；
 * (所以，应该是不能允许重复加入顶点的 )
 * 2.是否可以重复加入边（yes-覆盖）
 * --
 * 反思：
 * 1.关于 图的度，即顶点的度，类似 二叉树中节点的概念，都有跟节点相关联的线的概念。
 * 但是在有向图中，有入度和出度的概念。
 * --
 * 回顾：
 * 1.实现了图的基本接口（Vertex + Edge 的增删改查）
 * 2.bfs
 * 3.dfs
 * 4.topological - 通过 Kahn 算法（变体）实现
 * 5.生成树/支撑树（Spanning Tree）（连通图的极小连通子图，含有图中所有n个顶点，恰好只有 n-1 条边）
 * [讨论的连通图都是 无向] -> 最小生成树（Minimum Spanning Tree）实现：Prim or Kruskal
 * （如果每一条边的权值都不相同，那么 MST 只有一个；否则就有多个）
 * 6.最短路径（shortest path）(起始顶点到终止顶点的权重最小的路径）（不允许有负权环）
 * [实现：1.Dijkstra 不允许有负权边；]
 */
public class AdjacencyListGraphV0<V, E> implements Graph<V, E> {

	//region	variable

	/**
	 * 图中顶点的个数
	 */
	private int verticesSize = 0;
	/**
	 * 图中边的个数
	 */
	private int edgesSize = 0;

	/**
	 * 记录图中的顶点集合
	 * （由于 图中不考虑顶点的先后顺序，于是直接使用 Set）
	 * 由于 V 是外部关系的，所以用 HashMap<V, Vertex>
	 */
	//private Set<Vertex<V, E>> vertextSet = new HashSet<>();
	private HashMap<V, Vertex<V, E>> vertexMap = new HashMap<>();

	/**
	 * 记录图中的边集合
	 * （由于 图中不考虑边的先后顺序，于是直接使用 Set）
	 */
	private Set<Edge<V, E>> edgeSet = new HashSet<>();

	/**
	 *
	 */
	private WeightManager<E> weightManager;

	//endregion

	//region	constructor

	/**
	 * no arg
	 */
	public AdjacencyListGraphV0() {
	}

	/**
	 * {@link com.sourcetrip.algorithm.inter.Graph.WeightManager} 鉴于设计模式抽离出来的独立接口
	 *
	 * @param weightManager
	 */
	public AdjacencyListGraphV0(WeightManager<E> weightManager) {
		this.weightManager = weightManager;
	}

	//endregion


	@Override
	public int verticesSize() {
		return verticesSize;
	}

	@Override
	public int edgesSize() {
		return edgesSize;
	}

	/**
	 * 在图中添加一个顶点
	 * （1.是否可以重复加入顶点？--由于已经不考虑位置关系，所以不能重复加入）
	 *
	 * @param v
	 */
	@Override
	public void addVertex(V v) {
		//往顶点集合里添加新的顶点（如果存在 equals 的顶点，就不再进行添加）-> 需要重写 equals 和 hashCode
		//-> 不以 inDegrees 和 outDegrees 作为判断条件
		if (!vertexMap.containsKey(v)) {
			vertexMap.put(v, new Vertex<>(v));
			verticesSize++;
		}

	}

	/**
	 * 需要额外移除相关的边
	 *
	 * @param v
	 */
	@Override
	public void removeVertex(V v) {
		Vertex<V, E> deleteVertex = vertexMap.get(v);
		if (deleteVertex == null) {
			return;
		}
		//如果不为空，开始进行删除业务
		//1.寻找出度和入度中的顶点，删除他们的边
		for (Edge<V, E> edge :
				deleteVertex.indegrees) {
			//寻找 from
			Vertex<V, E> fromVertex = edge.from;
			fromVertex.outdegrees.remove(edge);
		}

		for (Edge<V, E> edge :
				deleteVertex.outdegrees) {
			//寻找 from
			Vertex<V, E> toVertex = edge.to;
			toVertex.indegrees.remove(edge);
		}


		Iterator<Edge<V, E>> iterator = edgeSet.iterator();
		while (iterator.hasNext()) {
			Edge<V, E> edge = iterator.next();
			if (Objects.equals(edge.from, deleteVertex) || Objects.equals(edge.to, deleteVertex)) {
				iterator.remove();
			}
		}
//		for (Edge<V, E> edge :
//				edgeSet) {
//			if (Objects.equals(edge.from, vertexMap.get(v)) || Objects.equals(edge.to, vertexMap.get(v))) {
//				edgeSet.remove(edge);
//			}
//		}

		vertexMap.remove(v);
		verticesSize--;
	}

	/**
	 * 在图中加一条边
	 * 1.如果 from -> to 之间存在边 -> 覆盖 weight = null
	 *
	 * @param fromV 出来的顶点
	 * @param toV   到达的顶点
	 */
	@Override
	public void addEdge(V fromV, V toV) {
		addEdge(fromV, toV, null);
	}

	@Override
	public void addEdge(V fromV, V toV, E weight) {
		//为了防止没有顶点，先进行添加
		addVertex(fromV);
		addVertex(toV);
		Vertex<V, E> fromVertex = vertexMap.get(fromV);
		Vertex<V, E> toVertex = vertexMap.get(toV);
		Edge edge = new Edge(fromVertex, toVertex, weight);
		//如果原先已经有了 from 和 to -> 进行更新
		// 由于 hashSet add 时如果 key 相同，会造成无法覆盖并且 add() 返回 false,于是先进行 remove
//		if (edgeSet.add(edge)) {
//			//如果添加的是新的
//			//->维护 定点的 inDegrees 和 outDegrees
//			fromVertex.outdegrees.add(edge);
//			toVertex.indegrees.add(edge);
//		}
		edgeSet.remove(edge);
		fromVertex.outdegrees.remove(edge);
		toVertex.indegrees.remove(edge);

		edgeSet.add(edge);
		fromVertex.outdegrees.add(edge);
		toVertex.indegrees.add(edge);

		edgesSize++;
	}

	/**
	 * 根据起点和终点将 边删除
	 *
	 * @param fromV 边的起始顶点
	 * @param toV   边的到达顶点
	 */
	@Override
	public void removeEdge(V fromV, V toV) {
		Vertex<V, E> fromVertex = vertexMap.get(fromV);
		Vertex<V, E> toVertex = vertexMap.get(toV);
		Iterator<Edge<V, E>> iterator = edgeSet.iterator();
		while (iterator.hasNext()) {
			Edge<V, E> edge = iterator.next();
			if (Objects.equals(edge.from, fromVertex) && Objects.equals(edge.to, toVertex)) {
				iterator.remove();
			}
		}

		//1.找到边
//		for (Edge<V, E> edge :
//				edgeSet) {
//			if (Objects.equals(edge.from, fromVertex)&& Objects.equals(edge.to, toVertex)){
//				edgeSet.remove(edge);
//			}
//		}

		edgesSize--;
	}

	@Override
	public void print() {
		System.out.println("[顶点]-------------------");
		vertexMap.forEach((V v, Vertex<V, E> vertex) -> {
			System.out.println(v);
			System.out.println("out-----------");
			System.out.println(vertex.outdegrees);
			System.out.println("in-----------");
			System.out.println(vertex.indegrees);
		});

		System.out.println("[边]-------------------");
		edgeSet.forEach((Edge<V, E> edge) -> {
			System.out.println(edge);
		});
	}

	/**
	 * 从 begin 开始做深度优先遍历
	 * 即优先从访问顶点 outDegrees 的一条边的距离开始访问，一条边一条边地拓展开！
	 *
	 * @param begin   遍历的顶点（从不同的顶点访问的效果不一样，有可能不会遍历到所有的顶点）
	 * @param visitor 访问器
	 */
	@Override
	public void bfs(V begin, Visitor<V> visitor) {
		if (!vertexMap.containsKey(begin)) {
			return;
		}
		Vertex<V, E> vertex = vertexMap.get(begin);
		bfsByLoop(vertex, visitor);
	}

	/**
	 * 通过迭代的方式
	 *
	 * @param vertex  访问的顶点
	 * @param visitor
	 */
	private void bfsByLoop(Vertex<V, E> vertex, Visitor<V> visitor) {
		//1.建立一个队列进行辅助
		Queue<Vertex<V, E>> queue = new LinkedList<>();
		//记录已经访问过的顶点，避免重复访问
		HashSet<Vertex<V, E>> visitedSet = new HashSet<>();
		queue.offer(vertex);
		while (!queue.isEmpty()) {
			Vertex<V, E> cur = queue.poll();
			if (visitedSet.contains(cur)) {
				continue;
			}
			//执行访问
			if (visitor.stop) {
				break;
			}
			visitor.visit(cur.value);
			visitedSet.add(cur);
			for (Edge<V, E> item :
					cur.outdegrees) {
				queue.offer(item.to);
			}

		}

	}

	/**
	 * depth first search 深度优先搜索
	 * （先从一条路找到最深，再回退一步）
	 * 其实二叉树的前序遍历就是DFS
	 *
	 * @param begin   遍历的顶点（从不同的顶点访问的效果不一样，有可能不会遍历到所有的顶点）
	 * @param visitor 访问器
	 */
	@Override
	public void dfs(V begin, Visitor<V> visitor) {
		if (!vertexMap.containsKey(begin)) {
			return;
		}
		Vertex<V, E> vertex = vertexMap.get(begin);
		//dfsByLoop(vertex, visitor);
		dfsByRecursive(vertex, visitor, new HashSet<Vertex<V, E>>());
	}

	/**
	 * 拓扑排序（通过 Kahn 算法实现）
	 * 原 Kahn algorithm：
	 * 0.假设 L 是存放拓扑排序结果的列表；
	 * 1.把 所有 入度=0 的顶点放入 L 中，然后把这些顶点从图中去掉；
	 * 2.重复上，知道找不到 入度=0 的顶点。
	 * 如果此时L中元素和顶点总数相同，说明拓扑排序完成；
	 * 如果此时L中元素少于顶点总数，说明原图中存在环，无法进行拓扑排序。
	 * --
	 * 改进：利用一个辅助列表记录元素和入度的值，模拟删除。
	 *
	 * @return
	 */
	@Override
	public List<V> topologicalSort() {
		List<V> list = new ArrayList<>();
		topologicalSortByKahn(list);

		return list;
	}

	/**
	 * 最小生成树
	 *
	 * @return
	 */
	@Override
	public Set<EdgeInfo<V, E>> mst() {
		//return mstByPrim();
		return mstByKruskal();
	}

	/**
	 * 最短路径算法的实现。
	 * 单源：
	 * 1.Dijkstra
	 * 2.
	 * 多源：
	 * 1.
	 *
	 * @param vertexBegin 起始顶点
	 * @return
	 */
	@Override
	public Map<V, PathInfo<V, E>> shortestPath(V vertexBegin) {
		return spByDijkstra(vertexBegin);
	}

	/**
	 * 我自己实现的 Dijkstra 最短路径算法
	 * 1.基于一个 HashMap(Edge, 剩余权重) map
	 * 2.从 begin 寻找出度并加入 map
	 * 3.找到 map 中最小的权重值 -> 删除并同时减去 map 中其他的权重值 -> 直到 value =0 的元素出现
	 * -> 重复上述步骤直到 Edge 的终点边 = end && 权重值 == 0
	 * --
	 * 这里需要一个相减
	 * --
	 * 这个似乎只适合针对一个顶点的最短路径，如果要实现所有顶点的还不太好办啊。
	 *
	 * @param vertexBegin
	 * @return
	 */
	private Map<V, PathInfo<V, E>> spByDijkstraMine(V vertexBegin) {
		Map<V, PathInfo<V, E>> res = new HashMap<>();
		//开始的顶点
		Vertex<V, E> begin = vertexMap.get(vertexBegin);
		if (begin == null) {
			//临界判断
			return res;
		}
		//1.遍历所有的顶点集合，将顶点添加到 res 中
		for (Map.Entry<V, Vertex<V, E>> item :
				vertexMap.entrySet()) {
			res.put(item.getKey(), null);
		}
		//2.
		HashMap<Edge<V, E>, E> map = new HashMap<>();
		for (Edge<V, E> edge :
				begin.outdegrees) {
			//res.put(edge)
		}
		return res;
	}

	/**
	 * Dijkstra 算法实现的最短路径（类似 Prim(),但是更像是 贪心或者是 动态规划）
	 * 1.从 beginVertex 中找到 minPath ，松弛 minPath 的 to 的 out degrees 的距离：
	 * 就是更新 beginVertex 到 minPath.to.outDegrees 的 weight,即 value = add(minPath.weight, edge.weight).
	 * 这样可以叠加 path的 weight
	 * 2.重复上述
	 * --
	 * 感觉 Dijkstra 虽然算法不复杂，但是真的写起来的时候又不简单！
	 * --
	 * 感觉 Dijkstra 跟 BFS 很像，但是不同，是【拓展表】，跟接近动态规划
	 * 感觉难点在于使用什么用的数据结构比较便利：
	 * 针对 v -> 对应多条路径，以及是否存在环。想多搞一个数据结构了。
	 * --
	 *
	 * @param vertexBegin 起始顶点
	 * @return
	 */
	private Map<V, PathInfo<V, E>> spByDijkstra(V vertexBegin) {
		//最终选择的最短路径
		Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
		//顶点
		Vertex<V, E> beginVertex = vertexMap.get(vertexBegin);
		if (beginVertex == null) {
			return selectedPaths;
		}

		//保存 各个顶点的路径（当前已知的最短路径）
		Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
		//第一次可以弹出 beginVertex 的路径
		paths.put(beginVertex, new PathInfo<>(weightManager.zero()));

		while (!paths.isEmpty()) {
			//1.找到最短的边集合 minEntry
			Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
			//2.找到 minVertex，准备对其 out degrees 进行松弛
			Vertex<V, E> minVertex = minEntry.getKey();
			PathInfo<V, E> minPath = minEntry.getValue();
			//3.由于 minVertex 已经离开桌面，所以直接添加到
			selectedPaths.put(minVertex.value, minPath);
			//将备选路径中移除
			paths.remove(minVertex);
			//4.进行松弛
			for (Edge<V,E> item:
				 minVertex.outdegrees) {
				//如果 已经能确认了最短路径，那就不用对边进行松弛
				if (selectedPaths.containsKey(item.to.value)) {
					continue;
				}
				if (paths.containsKey(item.to)){
					//需要跟备选路径进行比较，有可能需要更新
					//比较最短路径
					E newWeight = weightManager.add(minPath.getWeight(), item.weight);

					PathInfo<V, E> oldPath = paths.get(item.to);
					if (weightManager.compare(newWeight, oldPath.getWeight()) >= 0) {
						//如果此时找到的路径 大于 旧的路径 -> 不处理
						continue;
					}
					//如果 找到的路径小于 旧的路径 -> 更新

					oldPath.getEdgeInfos().clear();
					//保存全路径
					oldPath.getEdgeInfos().addAll(minPath.getEdgeInfos());
					oldPath.getEdgeInfos().add(item.getEdgeInfo());
					oldPath.setWeight(newWeight);

				}else {
					//path info 是可以叠加的
					PathInfo<V, E> pathInfo = new PathInfo<>(weightManager.add(minPath.getWeight(), item.weight));
					pathInfo.getEdgeInfos().addAll(minPath.getEdgeInfos());
					pathInfo.addEdgeInfo(item.getEdgeInfo());
					//如果没有包含 -> 将当前路径添加进去，作为当前的最短路径
					paths.put(item.to, pathInfo);
				}
			}
		}
		selectedPaths.remove(vertexBegin);
		return selectedPaths;
	}

	/**
	 * 从 path map 中获取 minimum path
	 * @param paths
	 * @return
	 */
	private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
		Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
		Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
		if (minEntry == null){
			return minEntry;
		}
		Map.Entry<Vertex<V, E>, PathInfo<V, E>> curEntry;
		while (iterator.hasNext()){
			curEntry = iterator.next();
			if (weightManager.compare(minEntry.getValue().getWeight(), curEntry.getValue().getWeight())>0){
				minEntry = curEntry;
			}
		}
		return minEntry;
	}


	/**
	 * 通过 Prim 算法实现的 Minimum Spanning Tree
	 * 1.从 vertexMap 中拿到任意一个 vertex ,进行切分（cut）；
	 * 2.找到 横切边（Crossing Edge）中的权重最小的边，保留到 边集，并对该边的另一个顶点添加到 顶点集合中。
	 * 重复上述步骤。
	 * --
	 * 需要借助小顶堆快速完成。
	 * （只考虑无向图）
	 * --
	 * 跟 Kruskal 相比：
	 * Prim: 从顶点入手
	 * Kruskal:	从边入手
	 *
	 * @return 边集
	 */
	private Set<EdgeInfo<V, E>> mstByPrim() {
		//结果 边集
		Set<EdgeInfo<V, E>> res = new HashSet<>();
		Iterator<Vertex<V, E>> iterator = vertexMap.values().iterator();
		if (!iterator.hasNext()) {
			//如果没有顶点，直接返回
			return res;
		}
		//当前节点
		Vertex<V, E> curVertex = iterator.next();
		PriorityQueue<Edge<V, E>> edgesHeap = new PriorityQueue<>();
		//Set<Edge<V, E>> visitedEdges = new HashSet<>();
		//访问过的顶点集合
		Set<Vertex<V, E>> visitedVertexSet = new HashSet<>();
		visitedVertexSet.add(curVertex);
		int size = vertexMap.size();
		Edge<V, E> minEdge = null;
		while (visitedVertexSet.size() < size) {
			//将所有的边加入 min heap
			curVertex.indegrees.forEach(p -> {
				//将限制改在最后获取边的地方，不然这里会有漏洞的！
				//因为 之前加过的边的顶点会跟后面的定点重合，造成二叉堆中仍然会存在非横切边
//				if (!visitedVertexSet.contains(p.from)) {
//					edgesHeap.offer(p);
//				}
				edgesHeap.offer(p);
			});

			//弹出权重最小的边 - 即完成 Minimum Spanning Tree 所需要的顶点
			//该边必须是【横切边】！
			do {
				minEdge = edgesHeap.poll();
			}
			while (visitedVertexSet.contains(minEdge.from));

			visitedVertexSet.add(minEdge.from);
			res.add(minEdge.getEdgeInfo());

			curVertex = minEdge.from;
		}

		return res;
	}

	/**
	 * 通过 Kruskal 实现的 Minimum Spanning Tree
	 * 算法核心：
	 * 按照权重顺序将边加入生成树中，直到生成树中含有 V-1 条边。（V 顶点个数）
	 * --
	 * 按照 Kruskal 的算法，不能使用 visitedVertexSet 的集合，而是使用边的集合。
	 * --
	 * 失策了，还是不能用 Prim() 的思路，果然得用并查集。
	 * 类似 {@link com.leetcode.根据数据结构分类.图.B_684_冗余连接} 的办法！
	 *
	 * @return
	 */
	private Set<EdgeInfo<V, E>> mstByKruskal() {
		//结果 边集
		Set<EdgeInfo<V, E>> res = new HashSet<>();
		//访问过的边的集合（只考虑两个端点）
		//Set<Edge<V, E>> visitedEdgeSet = new HashSet<>();
		if (edgesSize() == 0) {
			//没有边
			return res;
		}

		//存储 起点和终点的映射
		//假设没有平行边
		//HashMap<V, Set<V>> directionsMap = new HashMap<>();
		//发现使用 上面的数据结构不好使，不方便判断
		//于是改成了每一次遍历就将边的方向进行纠正 -> 从小到大（但是需要比较器）
		//只能进行两次判断了。
		// 记录边的集合（由于 key 必须允许重复，所以只能用 数组了）
		//HashMap<V, V> edgeMap = new HashMap<>();
		//创建一个二维数组，用于去除方向
		V[][] edgeArray = (V[][]) new Object[edgeSet.size() << 1][2];
		int arraySize = 0;

		PriorityQueue<Edge<V, E>> edgesHeap = new PriorityQueue<>();
		//将所有的边加入 小顶堆
		//同时过滤方向
		//每一次添加时都生成相反方向的键值对
		for (Edge<V, E> item :
				edgeSet) {
			boolean add = true;
			for (int i = 0; i < arraySize; i++) {
				if (edgeArray[i][0].equals(item.from.value) && edgeArray[i][1].equals(item.to.value)) {
					add = false;
					break;
				}
			}
			if (add) {
				edgeArray[arraySize][0] = item.from.value;
				edgeArray[arraySize][1] = item.to.value;
				arraySize++;
				edgeArray[arraySize][0] = item.to.value;
				edgeArray[arraySize][1] = item.from.value;
				arraySize++;
				edgesHeap.add(item);
			}
		}

		UnionFindCustomedObject<Vertex<V, E>> unionfind = new UnionFindCustomedObjectWithQuickUnion<>();

		//从 小顶堆中弹出权重最小的边
		Edge<V, E> curEdge = edgesHeap.poll();
		res.add(curEdge.getEdgeInfo());
		unionfind.union(curEdge.from, curEdge.to);
		//最终边的数量 = 顶点的数量-1
		int edgeNum = vertexMap.size() - 1;

		//循环从 小顶堆 中弹出 边
		//但是依然很难判断什么时候树已经是最小生成树了，感觉还得用并查集
		while (res.size() < edgeNum && !edgesHeap.isEmpty()) {
			curEdge = edgesHeap.poll();
			if (unionfind.isSame(curEdge.from, curEdge.to)) {
				//如果两个跟节点相同，说明属于 冗余连接（成环）
				continue;
			}
			unionfind.union(curEdge.from, curEdge.to);
			res.add(curEdge.getEdgeInfo());
		}
		return res;
	}

	/**
	 * 通过 Kahn算法（改进版） 进行拓扑排序
	 * 0.准备一个队列 queue,一个 vertex- inDegrees num 表
	 * 1.当表中 inDegrees 的 size ==0 时，添加到 queue;
	 * 2.queue 出队 curVertex，并根据 curVertex 的 outDegrees 进行修改，并进行上述检查。
	 * --
	 * 其实也是一种 BFS
	 *
	 * @param list
	 */
	private void topologicalSortByKahn(List<V> list) {
		//准备一个队列
		Queue<Vertex<V, E>> queue = new LinkedList<>();
		//准备一个 入度数量记录表
		HashMap<Vertex<V, E>, Integer> table = new HashMap<>();
		for (Map.Entry<V, Vertex<V, E>> item :
				vertexMap.entrySet()) {
			Vertex<V, E> vertex = item.getValue();
			if (vertex.indegrees.size() == 0) {
				queue.offer(vertex);
			}
			//当 size ==0 时可以不用入 table 了，因为后面用不到
			table.put(vertex, vertex.indegrees.size());
		}
		while (!queue.isEmpty()) {
			Vertex<V, E> curVertex = queue.poll();
			list.add(curVertex.value);

			for (Edge<V, E> item :
					curVertex.outdegrees) {
				Integer tempValue = table.get(item.to);
				if (--tempValue == 0) {
					//如果此时已经为0
					queue.offer(item.to);
				}
				//修改 table 中的数量
				table.put(item.to, tempValue);
			}
		}
	}

	/**
	 * 使用循环实现深度优先搜索
	 * 实现起来比 先序遍历还要简单一些！
	 *
	 * @param vertex
	 * @param visitor
	 */
	private void dfsByLoop(Vertex<V, E> vertex, Visitor<V> visitor) {
		//借助一个栈帮助存储路径上的顶点
		Stack<Vertex<V, E>> vertexStack = new Stack<>();
		//记录已经访问过的顶点，避免重复访问
		HashSet<Vertex<V, E>> visitedSet = new HashSet<>();
		vertexStack.push(vertex);
		while (!vertexStack.isEmpty()) {
			Vertex<V, E> curVertex = vertexStack.pop();
			while (true) {
				//visit
				if (visitor.stop) {
					break;
				}
				if (!visitedSet.contains(curVertex)) {
					visitor.visit(curVertex.value);
					visitedSet.add(curVertex);
				}

				//找到了元素
				boolean found = false;
				for (Edge<V, E> item :
						curVertex.outdegrees) {
					if (!visitedSet.contains(item.to)) {
						curVertex = item.to;
						found = true;
						vertexStack.push(item.to);
						//找到第一个立即跳出循环
						break;
					}
				}
				if (!found) {
					break;
				}
			}
			//此时遍历完一条路

		}
	}

	/**
	 * 通过 递归实现 深度优先搜索
	 *
	 * @param vertex
	 * @param visitor
	 */
	private void dfsByRecursive(Vertex<V, E> vertex, Visitor<V> visitor, HashSet<Vertex<V, E>> visitedSet) {
		//region	visit
		if (visitor.stop) {
			return;
		}
		visitor.visit(vertex.value);
		visitedSet.add(vertex);
		//endregion

		for (Edge<V, E> item :
				vertex.outdegrees) {
			if (!visitedSet.contains(item.to)) {
				dfsByRecursive(item.to, visitor, visitedSet);
			}
		}
	}


	//region	inner class

	/**
	 * 顶点的类
	 * （由于只展示 Graph 的接口，所以作为内部类不让外界发现，Edge 同）
	 * 设计：
	 * 1.in-degree（入度）:关于从顶点进来的边；
	 * 2.out-degree（出度）：关于从顶点出去的边；
	 * 3.value：顶点的值
	 * 4.
	 */
	private static class Vertex<V, E> {

		/**
		 * 入度
		 */
		Set<Edge<V, E>> indegrees = new HashSet<>();
		/**
		 * 出度
		 */
		Set<Edge<V, E>> outdegrees = new HashSet<>();

		/**
		 * 顶点中存的值
		 */
		V value;

		public Vertex(V value) {
			this.value = value;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;
			Vertex<?, ?> vertex = (Vertex<?, ?>) o;
			return Objects.equals(value, vertex.value);
		}

		@Override
		public int hashCode() {
			return Objects.hash(value);
		}

		@Override
		public String toString() {
			return value == null ? "null" : value.toString();
		}

	}

	/**
	 * 顶点之间的边，由于是有向边，所以必然设置 from to
	 * 设计：
	 * 1.from :边的起点；
	 * 2.to :边的终点
	 */
	private static class Edge<V, E> implements Comparable<Edge<V, E>> {

		Vertex<V, E> from;
		Vertex<V, E> to;
		E weight;

		public Edge(Vertex<V, E> from, Vertex<V, E> to, E weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		/**
		 * @param from
		 * @param to
		 */
		public Edge(Vertex<V, E> from, Vertex<V, E> to) {
			this.from = from;
			this.to = to;
			weight = null;
		}

		/**
		 * 边的相等是根据 from 和 to 来判断的
		 *
		 * @param o
		 * @return
		 */
		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;
			Edge<?, ?> edge = (Edge<?, ?>) o;
			return from.equals(edge.from) && to.equals(edge.to);
		}

		@Override
		public int hashCode() {
			return Objects.hash(from, to);
		}

		@Override
		public String toString() {
			return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
		}

		/**
		 * 边的比较默认对 weight(权重) 进行比较
		 *
		 * @param o
		 * @return
		 */
		@Override
		public int compareTo(Edge<V, E> o) {
			return ((Comparable) this.weight).compareTo(o.weight);
		}

		/**
		 * 生成 EdgeInfo
		 *
		 * @return
		 */
		public EdgeInfo<V, E> getEdgeInfo() {
			return new EdgeInfo<V, E>(this.from.value, this.to.value, this.weight);
		}
	}
}